package com.example.demo.solution;

import java.util.*;

/**
 * @desc: 如何在数组中找到和为 “特定值” 的两个数<br/>
 * @author: Jingbo Hu<br/>
 * @time：2020年09⽉28⽇<br/>
 * @version：v1.0.0<br>
 */
public class FindSumNumbers {


    public static List<List<Integer>> twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        List<List<Integer>> resultList = new ArrayList<>();
        for (int i = 1; i < nums.length; i++) {
            // 去掉第一个元素，与下面完整的数组进行比较，使用完之后删除元素
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (map.containsKey(other) && map.get(other) != i) {
                resultList.add(Arrays.asList(i, map.get(other)));
                //为防止找到重复的元素对，匹配后从哈希表删除对应元素
                map.remove(nums[i]);
            }
        }
        return resultList;
    }

    /**
     * 对上面方法优化
     *
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> twoSumV2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        List<List<Integer>> resultList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (map.containsKey(other)) {
                resultList.add(Arrays.asList(map.get(other), i));
            }
            map.put(nums[i], i);
        }
        return resultList;
    }

    public static void main(String[] args) {
        int[] nums = {5, 12, 6, 3, 9, 2, 1, 7};
//        List<List<Integer>> lists = twoSum(nums, 13);
        List<List<Integer>> lists = twoSumV2(nums, 13);
        for (List<Integer> list : lists) {
            System.out.println(Arrays.toString(list.toArray()));
        }
    }
}
